// 第450题

//给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
//根节点的引用。 
//
// 一般来说，删除节点可分为两个步骤： 
//
// 
// 首先找到需要删除的节点； 
// 如果找到了，删除它。 
// 
//
// 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。 
//
// 示例: 
//
// 
//root = [5,3,6,2,4,null,7]
//key = 3
//
//    5
//   / \
//  3   6
// / \   \
//2   4   7
//
//给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
//
//一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
//
//    5
//   / \
//  4   6
// /     \
//2       7
//
//另一个正确答案是 [5,2,6,null,4,null,7]。
//
//    5
//   / \
//  2   6
//   \   \
//    4   7
// 
// Related Topics 树 
// 👍 377 👎 0

package tree.leetcode.editor.cn;

import com.dq.tree.TreeNode;
import sun.reflect.generics.tree.Tree;

public class DeleteNodeInABst {
    public static void main(String[] args) {
        Solution solution = new DeleteNodeInABst().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {

        return delete(root,key);
    }
    private TreeNode delete(TreeNode root, int key){
        if(root == null) return null;
        if(root.val>key){
            root.left = delete(root.left, key);
        }else if(root.val<key){
            root.right = delete(root.right, key);
        }else if(root.val==key){
            if(root.left==null) return root.right;
            if(root.right==null) return root.left;
            if(root.right.left!=null){
                TreeNode minParent = getRightMinParent(root.right);
                TreeNode newRoot = swapNodeIn(root, minParent.left);
                minParent.left = delete(root,key);
                return newRoot;
            }else{
                root.right.left = root.left;
                return root.right;
            }

        }
        return root;

    }

    private TreeNode swapNodeIn(TreeNode node1,TreeNode node2){
        TreeNode left=node1.left,right=node1.right;
        node1.left = node2.left;
        node1.right = node2.right;
        node2.left = left;
        node2.right = right;
        return node2;
    }
    //得到最小节点的父节点
    private TreeNode getRightMinParent(TreeNode root){

        while(root.left.left!=null) root = root.left;
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}